In general, digital watermarking is the embedding of information within a signal in such a way as to minimize the perception of the existence of the information in the signal. It is to be understood that watermarks as that term is used herein include information that is to be hidden in a signal.
Watermarking technologies are widely used in multimedia (picture, audio, video and audiovisual works) security applications, such as, for example, multimedia copyright protection, transaction tracking, or access control. Such applications can typically tolerate the inevitable distortion caused by a watermark as human senses are not 100% accurate, and the embedded information is typically perceived as noise.
For the purposes of this patent document and its interpretation, pictures and video are each considered to be “images”. It is to be understand that “images” encompasses both pictures and video, and audiovisual works includes works that have both audio and image (pictures and/or video) components. Multimedia includes pictures, audio, video and audiovisual works, alone or in combination.
Various watermarking schemes have been developed to fit design requirements of particular applications. For example, ownership protection needs an ownership-indicating watermark to survive common processing and intentional attacks (be “robust”). However, for tampering detection applications, the embedded secondary data (watermark) is used to determine whether the host media has been tampered with or not, so only fragile or semi-fragile watermarks (robust to common processing, but fragile to intentional attacks) are expected for this kind of application.
Most recently reported schemes cast watermarking into the transform domain (see for example J. Cox, J. Kilian, T. Leighton, and T. G. Shamoon, “Secure Spread Spectrum Watermarking for Multimedia,” in Proceedings of the IEEE International Conference on Image Processing, ICIP '97, Vol. 6, pp. 1673-1687, October 1997, or I. J. Cox, M. L. Miller and J. A. Bloom, Digital Watermarking, Morgan Kaufmann, 2001), due to the fact that transform domain watermarking schemes tend to achieve both perceptual transparency and robustness better than spatial/time domain schemes.
Again, a transform can be applied to all or a portion (subset) of a digitized work. As an example, a multimedia signal for watermark embedding may comprise a transform of the grey level of a digitized image. The watermark information is embedded in the signal subset. The watermark information is embedded in that signal. As will be evident to those skilled in the art, a transformed signal may be created from many different aspects of a work.
It is to be understood that a signal is not limited to representations of multimedia works, but could simply be another form of data carrying signal, or even a noise signal; provided that the signal can accept some distortion for its intended purpose.
Notwithstanding that a signal may originate from an analog or digital signal and that a watermarked signal may become a digital or an analog signal, watermarks are embedded in signal points (digitized elements) of a signal. Signal subsets may be processed as separate signals, or the subsets may form part of a signal encompassing a superset of subsets or an entire original signal. In the former case, it is to be recognized that a signal subset can itself be a signal. In the latter case, a watermark may be embedded in the signal subset without separation from the signal by processing at the time of embedding.
In terms of different robustness requirements, watermarking schemes can be divided into robust watermark, fragile watermark and semi-fragile watermark. In a robust watermark system, the embedded data can survive common signal processing operation, whereas fragile watermark becomes undetectable after even minor modification. Semi-fragile watermark is a hybrid of the above, only distortions exceeding a user-specified threshold will break the watermark.
Based on the employed embedding mechanism, existing watermarking schemes can be classified into two categories. In blind embedding algorithms, the embedded data have no relation to the host data. Additive spread spectrum algorithm (see for example J. Cox, J. Kilian, T. Leighton, and T. G. Shamoon, cited above), is a representative of this category. In the second category, data hiding is achieved by enforcing a relationship between the bits to be embedded and the marked values. Quantization based watermarking schemes are in this category. Quantization based watermarking algorithms embed the watermark, which is often a binary sequence, into the host data by quantizing the host signal with watermark associated quantizers.
The look-up table (LUT) base watermarking method is a type of quantization based watermarking. A LUT is a set of quantized values. For binary watermarking, each quantized value in a LUT carries either side information “1” or “0”. A general LUT watermark embedding method maps the original data to the closest quantized value associated with the desired watermark information bit in a look-up table. The embedded watermark can then be extracted from the received image by looking at the LUT.
The odd-even embedding is a simplest case of LUT embedding, the table entries for embedding “1” and “0” are arranged in an interleaving order, which is also formulated as run of 1 LUT embedding (see for example Wu, Multimedia Data Hiding, Ph.D. thesis, Princeton University, 2000). “Run” means the largest number of the consecutive 0's or 1's. The larger the run, the better the robustness.
In the design of any robust watermarking scheme, robustness against data distortion through signal processing or intentional attacks and the similarity between the signal before and after watermarking are two major requirements. For some watermarking applications, watermarks designed to survive normal processing and to resist any attempt by an adversary to thwart their intended purpose. In designing a robust watermark, it is important to identify the specific processes that are likely to occur between embedding and detection. Examples of processes a watermark might need to survive include but are not limited to lossy compression, digital-to-analog-to-digital conversion, analog recording, printing and scanning, format conversion, and so on. For example, a video watermark designed for monitoring television advertisements needs to survive the various processes involved in broadcasting—digital-to-analog conversion, lossy compression, etc—but does not need to survive other processes, such as rotation or halftoning (see, for example, I. J. Cox, M. L. Miller and J. A. Bloom cited above).
For other watermarking applications, fidelity is the primary measure of concern. In these cases, the watermarked work must be indistinguishable from the original. For example, distortion-free data embedding is often required in a medical image watermarking system.
Clearly, various robustness and fidelity requirements are involved in watermarking scheme design. In applications where surviving a common signal processing operation is the primary concern, the robustness requirement should be satisfied first, then the fidelity is maximized as much as possible. In other applications, the prerequisite is the perceptual similarity between the unwatermarked and watermarked signal, the robustness needs to be maximized as much as possible.
Several methods and models have been proposed to theoretically analyze information hiding. Chen and Wornell introduced quantization index modulation (QIM) and theoretically proved that QIM achieves better robustness-distortion tradeoff than the current popular spread-spectrum methods (see B. Chen and G. W. Wornell, “Quantization Index Modulation: A Class of Provably Good Methods for Digital Watermarking and Information Embedding”, IEEE Trans. Inform. Theory, Vol. 47, pp. 1423-1443, May, 2001, and B. Chen and G. W. Wornell, “An Information-theoretic Approach to the Design of Robust Digital Watermarking Systems”, in Proc. Int. Conf. Acoust., Speech, Signal Processing, ICASSP '99, Vol. 4, pp. 2061-2064). Wu indicated that through a look-up table of nontrivial run, the probability of detection error can be considerably smaller than the traditional odd-even embedding (see M. Wu, “Joint Security and Robustness Enhancement for Quantization Based Data Embedding,” IEEE Trans. on Circuits and Systems for Video Tech, Vol. 13, pp. 831-841, August 2003). Optimal nonuniform quantization embedding has also been studied by Wu et. al. (see G. Wu, E.-H. Yang, and W. Sun, “Optimization strategies for quantization watermarking with application to image authentication,” Proc. Int. Conf. Acoust., Speech, Signal Processing, pp. 672-675, 2003). Information theoretic models for data hiding have been presented by Moulin et al and are used to determined data hiding capacity (see P. Moulin and J. A. O'Sullivan, “Information-theoretic analysis of information hiding,” Proc. Int. Conf. Acoust., Speech, Signal Processing, vol. 6, pp. 3630-3633, June 2000, and P. Moulin and M. K. Mihcak, “A framework for evaluating the data-hiding capacity of image sources,” IEEE Trans. on Image Processing, vol. 11, no. 9, pp. 1029-1042, September 2002). Alternative watermark embedding and detecting methods and devices are desirable.